package com.LeeCode;

/**
 * 和为奇数的子数组数目
 */

public class Code1524 {
    public static void main(String[] args) {

    }

    public int numOfSubarrays(int[] arr) {
        int MOD = 1000000007;
        int n = arr.length;

        // evenCount: 前缀和为偶数的个数
        // oddCount: 前缀和为奇数的个数
        int evenCount = 1; // 空前缀和为0（偶数）
        int oddCount = 0;

        int prefixSum = 0;
        long result = 0;

        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];

            if ((prefixSum & 1)== 0) {
                // 当前前缀和为偶数
                // 要使子数组和为奇数，需要减去前缀和为奇数的部分
                result = (result + oddCount) % MOD;
                evenCount++;
            } else {
                // 当前前缀和为奇数
                // 要使子数组和为奇数，需要减去前缀和为偶数的部分
                result = (result + evenCount) % MOD;
                oddCount++;
            }
        }

        return (int) result;
    }
}
